function MinCoinChange(coins) {
  var coins = coins.sort(function (a, b) {
    return b - a;
  });

  this.makeChange = function (amount) {
    var change = [],
      total = 0;
    for (var i = 0; i < coins.length; i++) {
      var coin = coins[i];
      while (total + coin <= amount) {
        change.push(coin);
        total += coin;
      }
    }
    return change;
  }
}
var coin = new MinCoinChange([1, 2, 5, 10]);
console.log(coin.makeChange(36));

//首先尝试最大面额找零，之后尝试次大面额找零，直到完全找零

// * 反例: 
// 要分析什么情况下贪心算法无效，
// 如果出现一组硬币25，6，5，1.由于1 + 5=6，当遇到10元时，按照贪心算法将分解为6 + 4 * 1，而其实为2 * 5.

// * 状态转移树中，若后一状态仅仅取决于上一个状态，就用贪心算法； 从步步最优，到达全局最优，只考虑当下
// * 若后一状态取决于之前的多个状态，就用动态规划。

// * 使用条件
// ! 1、该问题的全局最优解可以通过一步又一步获取的多个局部最优解而得到。
// ! 2、该问题包含多个子问题，而对子问题求解最优解有助于得到该问题的最优解。